// Date: 2022/01/20 16:36
// Note: 前缀和优化 & 二分查找

#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

template<typename T, typename Q>
class Solver {

    std::vector<T> packages;
    Q sum = 0;
    Q min_wasted_space = std::numeric_limits<Q>::max();
    T max_package_size = 0;
    T min_package_size = std::numeric_limits<T>::max();

public:
    Solver() = default;

    auto init(std::vector<T> const& packages_) {
        // 将包裹从小到大排序
        this->packages = packages_;
        std::sort(
            this->packages.begin(),
            this->packages.end(),
            std::less<T>()
        );
        this->max_package_size = this->packages.back();
        this->min_package_size = this->packages.front();
        this->sum = std::accumulate(packages.begin(), packages.end(), Q{0});
    }

    // 处理每个供货商的箱子列表
    auto fit(std::vector<T> const& boxes_) {
        auto boxes = boxes_;

        // 排序箱子大小
        std::sort(boxes.begin(), boxes.end(), std::less<T>());

        if (boxes.back() < this->max_package_size) { return; }

        auto wasted_space = Q{ 0 };         // 记录浪费的空间
        auto l = this->packages.begin();    // 包裹大小查找区间下界
        auto last = this->packages.end();   // 包裹大小查找区间上界

        // 尽可能用小箱子
        // 因此从小到大遍历可用箱子的大小
        // 不遍历过小的箱子

        auto i = std::lower_bound(begin(boxes), end(boxes), this->min_package_size);
        
        for ( ; i != end(boxes) && l != last; ++i) {  // 查找区间为空，退出算法
            auto box_size = *i;

            auto it = std::upper_bound(l, last, box_size);  // 查找可以装入当前箱子的最大包裹上界
            auto package_count = it - l;                    // 计算包裹数量
            wasted_space += package_count * box_size;

            l = it;  // 更新查找区间
        }

        wasted_space -= this->sum;

        // 更新结果
        if (wasted_space < this->min_wasted_space) {
            this->min_wasted_space = wasted_space;
        }
    }

    auto ans() {
        if (this->min_wasted_space == std::numeric_limits<Q>::max()) {
            return Q{ -1 };      // 结果未被更新，说明没有满足要求的答案
        }
        else {
            return min_wasted_space;
        }
    };
};

class Solution {
public:
    static int minWastedSpace(std::vector<int>& packages, std::vector<std::vector<int>>& boxes) {
        Solver<int, long long> solver;
        solver.init(packages);

        for (auto const& box_list : boxes) {
            solver.fit(box_list);
        }

        constexpr int MOD = 1'000'000'000 + 7;
        return solver.ans() % MOD;
    }
};

#include <iostream>

int main() {
    std::vector<int> packages = { 7,6,5,3,4 };
    std::vector<std::vector<int>> boxes = {
        {2,7}, {6}, {10, 5}
    };
    std::cout << Solution::minWastedSpace(packages, boxes) << "\n";
}
